public class Solution12 {
    public String intToRoman(int num) {
        String s = "";
        s += getRoman(num / 1000, "", "", "M");
        num %= 1000;
        s += getRoman(num / 100, "M", "D", "C");
        num %= 100;
        s += getRoman(num / 10, "C", "L", "X");
        num %= 10;
        s += getRoman(num, "X", "V", "I");
        return s;

    }

    private String getRoman(int n, String ten, String five, String one) {
        if (n == 0)
            return "";
        if (n < 4) {
            return one.repeat(n);
        }
        if (n == 4)
            return one + five;
        if (n == 9)
            return one + ten;
        else
            return five + one.repeat(n - 5);
    }
}
